import java.util.Arrays;

public class CountingSortDemo {

	// finds the maximal element in an array
	static int getMax(int[] a) {
		if (a == null || a.length == 0) {
			return -1;
		}

		// there is at least one element
		int max = a[0];
		for (int i = 1; i < a.length; i++) {
			if (a[i] > max) {
				max = a[i];
			}
		}
		return max;
	}
	
	static void countingSort(int[] inputArray) {
		if (inputArray == null || inputArray.length == 0)	return ;
		int sizea = inputArray.length;
		int sizeb = getMax(inputArray) + 1;
		if (sizeb > 0) {
			int lastPositionInSortedArray[] = new int[sizeb];
			int[] result = new int[sizea];

			for (int j = 0; j < sizea; j++) {
				int value = inputArray[j];
				lastPositionInSortedArray[value]++;
			}

			lastPositionInSortedArray[0]--;
			for (int j = 1; j < sizeb; j++) {
				lastPositionInSortedArray[j] += lastPositionInSortedArray[j - 1];
			}
			
			for(int i=0; i<sizea; i++) {
				int value = inputArray[i];
				int indexInSortedArray = lastPositionInSortedArray[value]--;
				result[indexInSortedArray] = value;
			}
			
			copyArray(inputArray, result);
		}		
	}

	
	//copy second array into the first one
	private static void copyArray(int[] inputArray,int[] result) {
		if (inputArray == null || result == null) return ;
		
		for(int i=0; i<inputArray.length; i++) {
			inputArray[i] = result[i];
		}
	}

	public static void main(String[] args) {
		int a[] = { 1, 5, 5, 3, 8, 2, 3, 2, 1, 5, 8 };
		countingSort(a);
		printArray(a);
	}

	private static void printArray(int[] a) {
		for (int x : a) {
			System.out.print(x + " ");
		}
	}

}
